home *** CD-ROM | disk | FTP | other *** search
/ Hacker's Arsenal - The Cutting Edge of Hacking / Hacker's Arsenal - The Cutting Edge of Hacking.iso / texts / tcp-ip11.txt < prev    next >
Text File  |  2001-07-11  |  35KB  |  866 lines
  1.  
  2. Archive-name:tcp-ip/FAQ
  3. Last-modified:  1996/4/1
  4.  
  5. Internet Protocol Frequently Asked Questions
  6.  
  7. Maintained by: George V. Neville-Neil (gnn@wrs.com)
  8. Contributions from:
  9. Ran Atkinson
  10. Mark Bergman
  11. Stephane Bortzmeyer
  12. Rodney Brown
  13. Dr. Charles E. Campbell Jr.
  14. Phill Conrad 
  15. Alan Cox
  16. Rick Jones
  17. Jon Kay 
  18. Jay Kreibrich
  19. William Manning
  20. Barry Margolin 
  21. Jim Muchow
  22. Subu Rama
  23. W. Richard Stevens 
  24.  
  25. Version 3.3
  26.  
  27.  
  28. ************************************************************************
  29.  
  30.     The following is a list of Frequently Asked Questions, and
  31. their answers, for people interested in the Internet Protocols,
  32. including TCP, UDP, ICMP and others.  Please send all additions,
  33. corrections, complaints and kudos to the above address.  This FAQ will
  34. be posted on or about the first of every month.
  35.  
  36.     This FAQ is available for anonymous ftp from :
  37. ftp.netcom.com:/pub/gnn/tcp-ip.faq .  You may get it from my home page at
  38. ftp://ftp.netcom.com/pub/gnn/gnn.html
  39.     You can read the FAQ in HTMl format on Netcom or from the mirror 
  40. site http://web.cnam.fr/Network/TCP-IP/tcp-ip.html
  41.  
  42. ************************************************************************
  43.  
  44. Table of Contents:
  45. Glossary
  46. 1) Are there any good books on IP?
  47. 2) Where can I find example source code for TCP/UDP/IP?
  48. 3) Are there any public domain programs to check the performance of an
  49. IP link? 
  50. 4) Where do I find RFCs?
  51. 5) How can I detect that the other end of a TCP connection has
  52. crashed?  Can I use "keepalives" for this?
  53. 6) Can the keepalive timeouts be configured?
  54. 7) Can I set up a gateway to the Internet that translates IP
  55. addresses, so that I don't have to change all our internal addresses 
  56. to an official network? 
  57. 8) Are there object-oriented network programming tools?
  58. 9) What other FAQs are related to this one?
  59. 10) What newsgroups contain information on networks/protocols?
  60. 11) Van Jacobson explains TCP congestion avoidance.
  61. 12) Can I use a single bit subnet?
  62.  
  63. Glossary:
  64.  
  65. I felt this should be first given the plethora of acronyms used in the
  66. rest of this FAQ.
  67.  
  68. IP: Internet Protocol.  The lowest layer protocol defined in TCP/IP.
  69. This is the base layer on which all other protocols mentioned herein
  70. are built.  IP is often referred to as TCP/IP as well.
  71.  
  72. UDP: User Datagram Protocol.  This is a connectionless protocol built
  73. on top of IP.  It does not provide any guarantees on the ordering or
  74. delivery of messages.  This protocol is layered on top of IP.
  75.  
  76. TCP: Transmission Control Protocol.  TCP is a connection oriented
  77. protocol that guarantees that messages are delivered in the order in
  78. which they were sent and that all messages are delivered.  If a TCP
  79. connection cannot deliver a message it closes the connection and
  80. informs the entity that created it.  This protocol is layered on top
  81. of IP.
  82.  
  83. ICMP:  Internet Control Message Protocol.  ICMP is used for
  84. diagnostics in the network.  The Unix program, ping, uses ICMP
  85. messages to detect the status of other hosts in the net.  ICMP
  86. messages can either be queries (in the case of ping) or error reports,
  87. such as when a network is unreachable.
  88.  
  89. RFC: Request For Comment.  RFCs are documents that define the
  90. protocols used in the IP Internet.  Some are only suggestions, some
  91. are even jokes, and others are published standards.  Several sites in
  92. the Internet store RFCs and make them available for anonymous ftp.
  93.  
  94. SLIP:  Serial Line IP.  An implementation of IP for use over a serial
  95. link (modem).  CSLIP is an optimized (compressed) version of SLIP that
  96. gives better throughput.
  97.  
  98. Bandwidth:  The amount of data that can be pushed through a link in
  99. unit time.  Usually measured in bits or bytes per second.
  100.  
  101. Latency:  The amount of time that a message spends in a network going
  102. from point A to point B.
  103.  
  104. Jitter:  The effect seen when latency is not a constant.  That is, if
  105. messages experience a different latencies between two points in a
  106. network.
  107.  
  108. RPC:  Remote Procedure Call.  RPC is a method of making network access
  109. to resource transparent to the application programmer by supplying a
  110. "stub" routine that is called in the same way as a regular procedure
  111. call.  The stub actually performs the call across the network to
  112. another computer.
  113.  
  114. Marshalling:  The process of taking arbitrary data (characters,
  115. integers, structures) and packing them up for transmission across a
  116. network.
  117.  
  118. MBONE: A virtual network that is a Multicast backBONE.  It is still a
  119. research prototype, but it extends through most of the core of the
  120. Internet (including North America, Europe, and Australia).  It uses IP
  121. Multicasting which is defined in RFC-1112.  An MBONE FAQ is available
  122. via anonymous ftp from: ftp.isi.edu" There are frequent broadcasts of
  123. multimedia programs (audio and low bandwidth video) over the MBONE.
  124. Though the MBONE is used for mutlicasting, the long haul parts of the
  125. MBONE use point-to-point connections through unicast tunnels to
  126. connect the various multicast networks worldwide.
  127.  
  128.  
  129. 1) Are there any good books on IP?
  130.  
  131. A) Yes.  Please see the following:
  132.  
  133. Internetworking with TCP/IP Volume I
  134. (Principles, Protocols, and Architecture)
  135. Douglas E. Comer
  136. Prentice Hall 1991 ISBN 0-13-468505-9
  137.  
  138. This volume covers all of the protocols, including IP, UDP, TCP, and
  139. the gateway protocols.  It also includes discussions of higher level
  140. protocols such as FTP, TELNET, and NFS.
  141.  
  142. Internetworking with TCP/IP Volume II
  143. (Design, Implementation, and Internals)
  144. Douglas E. Comer / David L. Stevens
  145. Prentice Hall 1991  ISBN 0-13-472242-6
  146.  
  147. Discusses the implementation of the protocols and gives numerous code
  148. examples.
  149.  
  150. Internetworking with TCP/IP Volume III (BSD Socket Version)
  151. (Client - Server Programming and Applications)
  152. Douglas E. Comer / David L. Stevens
  153. Prentice Hall 1993  ISBN 0-13-474222-2
  154.  
  155. This book discusses programming applications that use the internet
  156. protocols.  It includes examples of telnet, ftp clients and servers.
  157. Discusses RPC and XDR at length.
  158.  
  159. TCP/IP Illustrated, Volume 1: The Protocols, 
  160. W. Richard Stevens
  161. (c) Addison-Wesley, 1994  ISBN 0-201-63346-9
  162.  
  163. An excellent introduction to the entire TCP/IP protocol suite,
  164. covering all the major protocols, plus several important applications.
  165.  
  166. "TCP/IP Illustrated, Volume 2: The Implementation",
  167. by Gary R. Wright and W. Richard Stevens
  168. (c) Addison-Wesley, 1995
  169. ISBN 0-201-63354-X
  170.  
  171. This is a complete, and lenthy, discussion of the internals of TCP/IP
  172. based on the Net/2 release of BSD.
  173.  
  174. Unix Network Programming
  175. W. Richard Stevens
  176. Prentice Hall 1990  ISBN 0-13-949876
  177.  
  178. An excellent introduction to network programming under Unix.
  179.  
  180. The Design and Implementation of the 4.3 BSD Operating System
  181. Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, John S.
  182. Quarterman 
  183. Addison-Wesley 1989  ISBN 0-201-06196-1
  184.  
  185. Though this book is a reference for the entire operating system, the
  186. eleventh and twelfth chapters completely explain how the networking
  187. protocols are implemented in the kernel.
  188.  
  189. Stevens, W. Richard, Unix Network Programming.  1990, Prentice-Hall.
  190.  
  191. An excellent introduction to network programming under Unix.   Widely
  192. cited on the Usenet bulliten boards as the "best place to start" if you
  193. want to actually learn how to write Unix programs that communicate over
  194. a network.  
  195.  
  196. Rago, Steven A.  Unix System V. Network Programming.  1993, Addison-Wesley.
  197.  
  198. A book that covers the same kinds of topics as W. Richard Stevens Unix
  199. Network Programming, but is more specific to Unix System V Release 4
  200. (SVR4), and so perhaps is more useful and up to date if you are
  201. working specifically with that implementation.  (Stevens book covers
  202. Unix System V release 3.x).  There is a much more extensive coverage
  203. of Streams in Rago's book; 4 chapters, where Stevens only provides a
  204. couple of subsections.  The design project at the end of the book is
  205. an implementation of SLIP.
  206.  
  207.  
  208. 2)  Where can I find example source code for TCP/UDP/IP?
  209.  
  210. A)  Code from the Internetworking with TCP/IP Volume III is available
  211. for anonymous ftp from:
  212.  
  213. arthur.cs.purdue.edu:/pub/dls
  214.  
  215. Code used in the Net-2 version of Berkeley Unix is available for
  216. anonymous ftp from:
  217.  
  218. ftp.uu.net:systems/unix/bsd-sources/sys/netinet 
  219.  
  220. and
  221.  
  222. gatekeeper.dec.com:/pub/BSD/net2/sys/netinet
  223.  
  224. Code from Richard Steven's book is available on:
  225. ftp.uu.net:/published/books/stevens.*
  226.  
  227. Example source code and libraries to make coding quicker is available
  228. in the Simple Sockets Library written at NASA.  The Simple Sockets
  229. Library makes sockets easy to use!  And, it comes as source code.  It
  230. has been tested on: Unix (SGI, DecStation, AIX, Sun 3, Sparcstation;
  231. version 2.02+: Solaris 2.1, SCO), VMS, and MSDOS (client only since
  232. there's no background there).  It is provided in source code form, of
  233. course, and sits atop Berkeley sockets and tcp/ip.
  234.  
  235. You can order the "Simple Sockets Library" from
  236.  
  237.                            Austin Code Works
  238.                           11100 Leafwood Lane
  239.                        Austin, TX 78750-3464 USA
  240.                          Phone (512) 258-0785
  241.                  
  242. Ask for the "SSL - The Simple Sockets Library".  Last I checked, they
  243. were asking $20 US for it.
  244.  
  245.  
  246. For DOS there is WATTCP.ZIP (numerous sites): 
  247.  
  248. WATTCP is a DOS TCP/IP stack derived from the NCSA Telnet program and
  249. much enhanced. It comes with some example programs and complete source
  250. code. The interface isn't BSD sockets but is well suited to PC type
  251. work. It is also written so that it can be used and memory
  252. allocation).
  253.  
  254. 3)  Are there any public domain programs to check the performance of
  255. an IP link?
  256.  
  257. A)  
  258.  
  259. TTCP:  Available for anonymous ftp from....
  260.  
  261. wuarchive.wustl.edu:/graphics/graphics/mirrors/sgi.com/sgi/src/ttcp
  262.  
  263. On ftp.sgi.com are netperf (from Rick Jones at HP) and nettest
  264. (from Dave Borman at Cray).  ttcp is also availabel at ftp.sgi.com.
  265.  
  266. You can get to the NetPerf home page via:
  267.  
  268. http://www.cup.hp.com/netperf/NetperfPage.html
  269.  
  270.  
  271. There is suite of Bandwidth Measuring programs from gnn@netcom.com.
  272. Available for anonymous ftp from ftp.netcom.com in
  273. ~ftp/gnn/bwmeas-0.3.tar.Z These are several programs that meausre
  274. bandwidth and jitter over several kinds of IPC links, including TCP
  275. and UDP.
  276.  
  277.  
  278. 4) Where do I find RFCs?
  279.  
  280. A)  This is the latest info on obtaining RFCs:
  281. Details on obtaining RFCs via FTP or EMAIL may be obtained by sending
  282. an EMAIL message to rfc-info@ISI.EDU with the message body 
  283. help: ways_to_get_rfcs.  For example:
  284.  
  285.         To: rfc-info@ISI.EDU
  286.         Subject: getting rfcs
  287.  
  288.         help: ways_to_get_rfcs
  289.  
  290. The response to this mail query is quite long and has been omitted.
  291.  
  292. RFCs can be obtained via FTP from DS.INTERNIC.NET, NIS.NSF.NET,
  293. NISC.JVNC.NET, FTP.ISI.EDU, WUARCHIVE.WUSTL.EDU, SRC.DOC.IC.AC.UK,
  294. FTP.CONCERT.NET, or FTP.SESQUI.NET.
  295.  
  296.  
  297. Using Web, WAIS, and gopher:
  298.  
  299. Web:
  300.  
  301. http://web.nexor.co.uk/rfc-index/rfc-index-search-form.html
  302.  
  303. WAIS access by keyword:
  304.  
  305. wais://wais.cnam.fr/RFC
  306.  
  307. Excellent presentation with a full-text search too:
  308.  
  309. http://www.cis.ohio-state.edu/hypertext/information/rfc.html
  310.  
  311. With Gopher:
  312.  
  313. gopher://r2d2.jvnc.net/11/Internet%20Resources/RFC
  314. gopher://muspin.gsfc.nasa.gov:4320/1g2go4%20ds.internic.net%2070%201%201/.ds/
  315. .internetdocs
  316.  
  317.  
  318.  
  319. 5) How can I detect that the other end of a TCP connection has crashed?
  320. Can I use "keepalives" for this?
  321.  
  322. A) Detecting crashed systems over TCP/IP is difficult.  TCP doesn't require
  323. any transmission over a connection if the application isn't sending
  324. anything, and many of the media over which TCP/IP is used (e.g. ethernet)
  325. don't provide a reliable way to determine whether a particular host is up.
  326. If a server doesn't hear from a client, it could be because it has nothing
  327. to say, some network between the server and client may be down, the server
  328. or client's network interface may be disconnected, or the client may have
  329. crashed.  Network failures are often temporary (a thin ethernet will appear
  330. down while someone is adding a link to the daisy chain, and it often takes
  331. a few minutes for new routes to stabilize when a router goes down), and TCP
  332. connections shouldn't be dropped as a result.
  333.  
  334. Keepalives are a feature of the sockets API that requests that an empty
  335. packet be sent periodically over an idle connection; this should evoke an
  336. acknowledgement from the remote system if it is still up, a reset if it has
  337. rebooted, and a timeout if it is down.  These are not normally sent until
  338. the connection has been idle for a few hours.  The purpose isn't to detect
  339. a crash immediately, but to keep unnecessary resources from being allocated
  340. forever.
  341.  
  342. If more rapid detection of remote failures is required, this should be
  343. implemented in the application protocol.  There is no standard mechanism
  344. for this, but an example is requiring clients to send a "no-op" message
  345. every minute or two.  An example protocol that uses this is X Display
  346. Manager Control Protocol (XDMCP), part of the X Window System, Version 11;
  347. the XDM server managing a session periodically sends a Sync command to the
  348. display server, which should evoke an application-level response, and
  349. resets the session if it doesn't get a response (this is actually an
  350. example of a poor implementation, as a timeout can occur if another client
  351. "grabs" the server for too long).
  352.  
  353. 6) Can the keepalive timeouts be configured?
  354.  
  355. A) This varies by operating system.  There is a program that works on
  356. many Unices (though not Linux or Solaris), called netconfig, that
  357. allows one to do this and documents many of the variables.  It is
  358. available by anonymous FTP from
  359.  
  360.     cs.ucsd.edu:pub/csl/Netconfig/netconfig2.2.tar.Z
  361.  
  362. In addition, Richard Stevens' TCP/IP Illustrated, Volume 1 includes a
  363. good discussion of setting the most useful variables on many
  364. platforms.
  365.  
  366.  
  367. 7) Can I set up a gateway to the Internet that translates IP addresses, so
  368. that I don't have to change all our internal addresses to an official
  369. network?
  370.  
  371. A) There's no general solution to this.  Many protocols include IP
  372. addresses in the application-level data (FTP's "PORT" command is the most
  373. notable), so it isn't simply a matter of translating addresses in the IP
  374. header.  Also, if the network number(s) you're using match those assigned
  375. to another organization, your gateway won't be able to communicate with
  376. that organization (RFC 1597 proposes network numbers that are reserved for
  377. private use, to avoid such conflicts, but if you're already using a
  378. different network number this won't help you).
  379.  
  380. However, if you're willing to live with limited access to the Internet from
  381. internal hosts, the "proxy" servers developed for firewalls can be used as
  382. a substitute for an address-translating gateway. See the firewall FAQ.
  383.  
  384. 8) Are there object-oriented network programming tools?
  385.  
  386. A) Yes, and one such system is called ACE (ADAPTIVE Communication
  387. Environment).  Here is how to get more information and the software:
  388.  
  389. OBTAINING ACE
  390.  
  391. An HTML version of this README file is available at URL
  392. http://www.cs.wustl.edu/~schmidt/ACE.html.  All software and
  393. documentation is available via both anonymous ftp and the Web.
  394.  
  395. ACE is available for anonymous ftp from the ics.uci.edu (128.195.1.1)
  396. host in the gnu/C++_wrappers.tar.Z file (approximately .5 meg
  397. compressed).  This release contains contains the source code,
  398. documentation, and example test drivers for C++ wrapper libras.
  399.  
  400. 9) What other FAQs might you want to look in?
  401. comp.protocols.tcp-ip.ibmpc
  402.    Aboba, Bernard D.(1994) "comp.protocols.tcp-ip.ibmpc Frequently
  403.     Asked Questions (FAQ)" Usenet news.answers, available via
  404.     file://ftp.netcom.com/pub/ma/mailcom/IBMTCP/ibmtcp.zip,
  405.     57 pages.
  406.  
  407. comp.protocols.ppp
  408.    Archive-name: ppp-faq/part[1-8]
  409.    URL: http://cs.uni-bonn.de/ppp/part[1-8].html
  410.  
  411. comp.dcom.lans.ethernet
  412.    ftp site: dorm.rutgers.edu, pub/novell/DOCS
  413.    Ethernet Network Questions and Answers
  414.    Summarized from UseNet group comp.dcom.lans.ethernet
  415.  
  416. 10) What other newsgroups deal with networking?
  417.  
  418. comp.dcom.cabling       Cabling selection, installation and use.
  419. comp.dcom.isdn          The Integrated Services Digital Network
  420.             (ISDN).
  421. comp.dcom.lans.ethernet Discussions of the Ethernet/IEEE 802.3
  422.             protocols.
  423. comp.dcom.lans.fddi     Discussions of the FDDI protocol suite.
  424. comp.dcom.lans.misc     Local area network hardware and software.
  425. comp.dcom.lans.token-ring       Installing and using token ring
  426.                 networks.
  427. comp.dcom.servers       Selecting and operating data communications
  428.             servers.
  429. comp.dcom.sys.cisco     Info on Cisco routers and bridges.
  430. comp.dcom.sys.wellfleet Wellfleet bridge & router systems hardware &
  431.             software.
  432. comp.protocols.ibm      Networking with IBM mainframes.
  433. comp.protocols.iso      The ISO protocol stack.
  434. comp.protocols.kerberos The Kerberos authentication server.
  435. comp.protocols.misc     Various forms and types of protocol.
  436. comp.protocols.nfs      Discussion about the Network File System
  437.             protocol.
  438. comp.protocols.ppp      Discussion of the Internet Point to Point
  439.             Protocol.
  440. comp.protocols.smb      SMB file sharing protocol and Samba SMB
  441.             server/client.
  442. comp.protocols.tcp-ip   TCP and IP network protocols.
  443. comp.protocols.tcp-ip.ibmpc     TCP/IP for IBM(-like) personal
  444.                 computers.
  445. comp.security.misc      Security isuipment for the PC.
  446. comp.os.ms-windows.networking.misc      Windows and other networks.
  447. comp.os.ms-windows.networking.tcp-ip    Windows and TCP/IP networking.
  448. comp.os.ms-windows.networking.windows   Windows' built-in networking.
  449. comp.os.os2.networking.misc     Miscellaneous networking issues of
  450.                 OS/2.
  451. comp.os.os2.networking.tcp-ip   TCP/IP under OS/2.
  452. comp.sys.novell         Discussion of Novell Netware products.
  453.  
  454. 11) Van Jacobson explains TCP congestion avoidance.
  455.  
  456. I've attached Van J's original posting on it (I seem to repost this every
  457. 6 months or so).  If you want to see some real examples of this in action,
  458. take a look at Chapter 21 of my "TCP/IP Illustrated, Volume 1".
  459.  
  460.     Rich Stevens
  461.  
  462. ---------------------------------------------------------------------------
  463. >From van@helios.ee.lbl.gov Mon Apr 30 01:44:05 1990
  464. To: end2end-interest@ISI.EDU
  465. Subject: modified TCP congestion avoidance algorithm
  466. Date: Mon, 30 Apr 90 01:40:59 PDT
  467. From: Van Jacobson <van@helios.ee.lbl.gov>
  468. Status: RO
  469.  
  470. This is a description of the modified TCP congestion avoidance
  471. algorithm that I promised at the teleconference.
  472.  
  473. BTW, on re-reading, I noticed there were several errors in
  474. Lixia's note besides the problem I noted at the teleconference.
  475. I don't know whether that's because I mis-communicated the
  476. algorithm at dinner (as I recall, I'd had some wine) or because
  477. she's convinced that TCP is ultimately irrelevant :).  Either
  478. way, you will probably be disappointed if you experiment with
  479. what's in that note.
  480.  
  481. First, I should point out once again that there are two
  482. completely independent window adjustment algorithms running in
  483. the sender:  Slow-start is run when the pipe is empty (i.e.,
  484. when first starting or re-starting after a timeout).  Its goal
  485. is to get the "ack clock" started so packets will be metered
  486. into the network at a reasonable rate.  The other algorithm,
  487. congestion avoidance, is run any time *but* when (re-)starting
  488. and is responsible for estimating the (dynamically varying)
  489. pipesize.  You will cause yourself, or me, no end of confusion
  490. if you lump these separate algorithms (as Lixia's message did).
  491.  
  492. The modifications described here are only to the congestion
  493. avoidance algorithm, not to slow-start, and they are intended to
  494. apply to large bandwidth-delay product paths (though they don't
  495. do any harm on other paths).  Remember that with regular TCP (or
  496. with slow-start/c-a TCP), throughput really starts to go to hell
  497. when the probability of packet loss is on the order of the
  498. bandwidth-delay product.  E.g., you might expect a 1% packet
  499. loss rate to translate into a 1% lower throughput but for, say,
  500. a TCP connection with a 100 packet b-d p. (= window), it results
  501. in a 50-75% throughput loss.  To make TCP effective on fat
  502. pipes, it would be nice if throughput degraded only as function
  503. of loss probability rather than as the product of the loss
  504. probabilty and the b-d p.  (Assuming, of course, that we can do
  505. this without sacrificing congestion avoidance.)
  506.  
  507. These mods do two things: (1) prevent the pipe from going empty
  508. after a loss (if the pipe doesn't go empty, you won't have to
  509. waste round-trip times re-filling it) and (2) correctly account
  510. for the amount of data actually in the pipe (since that's what
  511. congestion avoidance is supposed to be estimating and adapting to).
  512.  
  513. For (1), remember that we use a packet loss as a signal that the
  514. pipe is overfull (congested) and that packet loss can be
  515. detected one of two different ways:  (a) via a retransmit
  516. timeout or (b) when some small number (3-4) of consecutive
  517. duplicate acks has been received (the "fast retransmit"
  518. algorithm).  In case (a), the pipe is guaranteed to be empty so
  519. we must slow-start.  In case (b), if the duplicate ack
  520. threshhold is small compared to the bandwidth-delay product, we
  521. will detect the loss with the pipe almost full.  I.e., given a
  522. threshhold of 3 packets and an LBL-MIT bandwidth-delay of around
  523. 24KB or 16 packets (assuming 1500 byte MTUs), the pipe is 75%
  524. full when fast-retransmit detects a loss (actually, until
  525. gateways start doing some sort of congestion control, the pipe
  526. is overfull when the loss is detected so *at least* 75% of the
  527. packets needed for ack clocking are in transit when
  528. fast-retransmit happens).  Since the pipe is full, there's no
  529. need to slow-start after a fast-retransmit.
  530.  
  531. For (2), consider what a duplicate ack means:  either the
  532. network duplicated a packet (i.e., the NSFNet braindead IBM
  533. token ring adapters) or the receiver got an out-of-order packet.
  534. The usual cause of out-of-order packets at the receiver is a
  535. missing packet.  I.e., if there are W packets in transit and one
  536. is dropped, the receiver will get W-1 out-of-order and
  537. (4.3-tahoe TCP will) generate W-1 duplicate acks.  If the
  538. `consecutive duplicates' threshhold is set high enough, we can
  539. reasonably assume that duplicate acks mean dropped packets.
  540.  
  541. But there's more information in the ack:  The receiver can only
  542. generate one in response to a packet arrival.  I.e., a duplicate
  543. ack means that a packet has left the network (it is now cached
  544. at the receiver).  If the sender is limitted by the congestion
  545. window, a packet can now be sent.  (The congestion window is a
  546. count of how many packets will fit in the pipe.  The ack says a
  547. packet has left the pipe so a new one can be added to take its
  548. place.)  To put this another way, say the current congestion
  549. window is C (i.e, C packets will fit in the pipe) and D
  550. duplicate acks have been received.  Then only C-D packets are
  551. actually in the pipe and the sender wants to use a window of C+D
  552. packets to fill the pipe to its estimated capacity (C+D sent -
  553. D received = C in pipe).
  554.  
  555. So, conceptually, the slow-start/cong.avoid/fast-rexmit changes
  556. are:
  557.  
  558.   - The sender's input routine is changed to set `cwnd' to `ssthresh'
  559.     when the dup ack threshhold is reached.  [It used to set cwnd to
  560.     mss to force a slow-start.]  Everything else stays the same.
  561.  
  562.   - The sender's output routine is changed to use an effective window
  563.     of min(snd_wnd, cwnd + dupacks*mss)  [the change is the addition
  564.     of the `dupacks*mss' term.]  `Dupacks' is zero until the rexmit
  565.     threshhold is reached and zero except when receiving a sequence
  566.     of duplicate acks.
  567.  
  568. The actual implementation is slightly different than the above
  569. because I wanted to avoid the multiply in the output routine
  570. (multiplies are expensive on some risc machines).  A diff of the
  571. old and new fastrexmit code is attached (your line numbers will
  572. vary).
  573.  
  574. Note that we still do congestion avoidance (i.e., the window is
  575. reduced by 50% when we detect the packet loss).  But, as long as
  576. the receiver's offered window is large enough (it needs to be at
  577. most twice the bandwidth-delay product), we continue sending
  578. packets (at exactly half the rate we were sending before the
  579. loss) even after the loss is detected so the pipe stays full at
  580. exactly the level we want and a slow-start isn't necessary.
  581.  
  582. Some algebra might make this last clear:  Say U is the sequence
  583. number of the first un-acked packet and we are using a window
  584. size of W when packet U is dropped.  Packets [U..U+W) are in
  585. transit.  When the loss is detected, we send packet U and pull
  586. the window back to W/2.  But in the round-trip time it takes
  587. the U retransmit to fill the receiver's hole and an ack to get
  588. back, W-1 dup acks will arrive (one for each packet in transit).
  589. The window is effectively inflated by one packet for each of
  590. these acks so packets [U..U+W/2+W-1) are sent.  But we don't
  591. re-send packets unless we know they've been lost so the amount
  592. actually sent between the loss detection and the recovery ack is
  593. U+W/2+W-1 - U+W = W/2-1 which is exactly the amount congestion
  594. avoidance allows us to send (if we add in the rexmit of U).  The
  595. recovery ack is for packet U+W so when the effective window is
  596. pulled back from W/2+W-1 to W/2 (which happens because the
  597. recovery ack is `new' and sets dupack to zero), we are allowed
  598. to send up to packet U+W+W/2 which is exactly the first packet
  599. we haven't yet sent.  (I.e., there is no sudden burst of packets
  600. as the `hole' is filled.)  Also, when sending packets between
  601. the loss detection and the recovery ack, we do nothing for the
  602. first W/2 dup acks (because they only allow us to send packets
  603. we've already sent) and the bottleneck gateway is given W/2
  604. packet times to clean out its backlog.  Thus when we start
  605. sending our W/2-1 new packets, the bottleneck queue is as empty
  606. as it can be.
  607.  
  608. [I don't know if you can get the flavor of what happens from
  609. this description -- it's hard to see without a picture.  But I
  610. was delighted by how beautifully it worked -- it was like
  611. watching the innards of an engine when all the separate motions
  612. of crank, pistons and valves suddenly fit together and
  613. everything appears in exactly the right place at just the right
  614. time.]
  615.  
  616. Also note that this algorithm interoperates with old tcp's:  Most
  617. pre-tahoe tcp's don't generate the dup acks on out-of-order packets.
  618. If we don't get the dup acks, fast retransmit never fires and the
  619. window is never inflated so everything happens in the old way (via
  620. timeouts).  Everything works just as it did without the new algorithm
  621. (and just as slow).
  622.  
  623. If you want to simulate this, the intended environment is:
  624.  
  625.     - large bandwidth-delay product (say 20 or more packets)
  626.  
  627.     - receiver advertising window of two b-d p (or, equivalently,
  628.       advertised window of the unloaded b-d p but two or more
  629.       connections simultaneously sharing the path).
  630.  
  631.     - average loss rate (from congestion or other source) less than
  632.       one lost packet per round-trip-time per active connection.
  633.       (The algorithm works at higher loss rate but the TCP selective
  634.       ack option has to be implemented otherwise the pipe will go empty
  635.       waiting to fill the second hole and throughput will once again
  636.       degrade at the product of the loss rate and b-d p.  With selective
  637.       ack, throughput is insensitive to b-d p at any loss rate.)
  638.  
  639. And, of course, we should always remember that good engineering
  640. practise suggests a b-d p worth of buffer at each bottleneck --
  641. less buffer and your simulation will exhibit the interesting
  642. pathologies of a poorly engineered network but will probably
  643. tell you little about the workings of the algorithm (unless the
  644. algorithm misbehaves badly under these conditions but my
  645. simulations and measurements say that it doesn't).  In these
  646. days of $100/megabyte memory, I dearly hope that this particular
  647. example of bad engineering is of historical interest only.
  648.  
  649.  - Van
  650.  
  651. -----------------
  652. *** /tmp/,RCSt1a26717    Mon Apr 30 01:35:17 1990
  653. --- tcp_input.c    Mon Apr 30 01:33:30 1990
  654. ***************
  655. *** 834,850 ****
  656.                    * Kludge snd_nxt & the congestion
  657.                    * window so we send only this one
  658. !                  * packet.  If this packet fills the
  659. !                  * only hole in the receiver's seq.
  660. !                  * space, the next real ack will fully
  661. !                  * open our window.  This means we
  662. !                  * have to do the usual slow-start to
  663. !                  * not overwhelm an intermediate gateway
  664. !                  * with a burst of packets.  Leave
  665. !                  * here with the congestion window set
  666. !                  * to allow 2 packets on the next real
  667. !                  * ack and the exp-to-linear thresh
  668. !                  * set for half the current window
  669. !                  * size (since we know we're losing at
  670. !                  * the current window size).
  671.                    */
  672.                   if (tp->t_timer[TCPT_REXMT] == 0 ||
  673. --- 834,850 ----
  674.                    * Kludge snd_nxt & the congestion
  675.                    * window so we send only this one
  676. !                  * packet.
  677. !                  *
  678. !                  * We know we're losing at the current
  679. !                  * window size so do congestion avoidance
  680. !                  * (set ssthresh to half the current window
  681. !                  * and pull our congestion window back to
  682. !                  * the new ssthresh).
  683. !                  *
  684. !                  * Dup acks mean that packets have left the
  685. !                  * network (they're now cached at the receiver) 
  686. !                  * so bump cwnd by the amount in the receiver
  687. !                  * to keep a constant cwnd packets in the
  688. !                  * network.
  689.                    */
  690.                   if (tp->t_timer[TCPT_REXMT] == 0 ||
  691. ***************
  692. *** 853,864 ****
  693.                   else if (++tp->t_dupacks == tcprexmtthresh) {
  694.                       tcp_seq onxt = tp->snd_nxt;
  695. !                     u_int win =
  696. !                         MIN(tp->snd_wnd, tp->snd_cwnd) / 2 /
  697. !                         tp->t_maxseg;
  698.   
  699.                       if (win < 2)
  700.                           win = 2;
  701.                       tp->snd_ssthresh = win * tp->t_maxseg;
  702. - 
  703.                       tp->t_timer[TCPT_REXMT] = 0;
  704.                       tp->t_rtt = 0;
  705. --- 853,864 ----
  706.                   else if (++tp->t_dupacks == tcprexmtthresh) {
  707.                       tcp_seq onxt = tp->snd_nxt;
  708. !                     u_int win = MIN(tp->snd_wnd,
  709. !                             tp->snd_cwnd);
  710.   
  711. +                     win /= tp->t_maxseg;
  712. +                     win >>= 1;
  713.                       if (win < 2)
  714.                           win = 2;
  715.                       tp->snd_ssthresh = win * tp->t_maxseg;
  716.                       tp->t_timer[TCPT_REXMT] = 0;
  717.                       tp->t_rtt = 0;
  718. ***************
  719. *** 866,873 ****
  720.                       tp->snd_cwnd = tp->t_maxseg;
  721.                       (void) tcp_output(tp);
  722. ! 
  723.                       if (SEQ_GT(onxt, tp->snd_nxt))
  724.                           tp->snd_nxt = onxt;
  725.                       goto drop;
  726.                   }
  727.               } else
  728. --- 866,879 ----
  729.                       tp->snd_cwnd = tp->t_maxseg;
  730.                       (void) tcp_output(tp);
  731. !                     tp->snd_cwnd = tp->snd_ssthresh +
  732. !                                tp->t_maxseg *
  733. !                                tp->t_dupacks;
  734.                       if (SEQ_GT(onxt, tp->snd_nxt))
  735.                           tp->snd_nxt = onxt;
  736.                       goto drop;
  737. +                 } else if (tp->t_dupacks > tcprexmtthresh) {
  738. +                     tp->snd_cwnd += tp->t_maxseg;
  739. +                     (void) tcp_output(tp);
  740. +                     goto drop;
  741.                   }
  742.               } else
  743. ***************
  744. *** 874,877 ****
  745. --- 880,890 ----
  746.                   tp->t_dupacks = 0;
  747.               break;
  748. +         }
  749. +         if (tp->t_dupacks) {
  750. +             /*
  751. +              * the congestion window was inflated to account for
  752. +              * the other side's cached packets - retract it.
  753. +              */
  754. +             tp->snd_cwnd = tp->snd_ssthresh;
  755.           }
  756.           tp->t_dupacks = 0;
  757. *** /tmp/,RCSt1a26725    Mon Apr 30 01:35:23 1990
  758. --- tcp_timer.c    Mon Apr 30 00:36:29 1990
  759. ***************
  760. *** 223,226 ****
  761. --- 223,227 ----
  762.           tp->snd_cwnd = tp->t_maxseg;
  763.           tp->snd_ssthresh = win * tp->t_maxseg;
  764. +         tp->t_dupacks = 0;
  765.           }
  766.           (void) tcp_output(tp);
  767.  
  768. >From van@helios.ee.lbl.gov Mon Apr 30 10:37:36 1990
  769. To: end2end-interest@ISI.EDU
  770. Subject: modified TCP congestion avoidance algorithm (correction)
  771. Date: Mon, 30 Apr 90 10:36:12 PDT
  772. From: Van Jacobson <van@helios.ee.lbl.gov>
  773. Status: RO
  774.  
  775. I shouldn't make last minute 'fixes'.  The code I sent out last
  776. night had a small error:
  777.  
  778. *** t.c    Mon Apr 30 10:28:52 1990
  779. --- tcp_input.c    Mon Apr 30 10:30:41 1990
  780. ***************
  781. *** 885,893 ****
  782.                * the congestion window was inflated to account for
  783.                * the other side's cached packets - retract it.
  784.                */
  785. !             tp->snd_cwnd = tp->snd_ssthresh;
  786.           }
  787. -         tp->t_dupacks = 0;
  788.           if (SEQ_GT(ti->ti_ack, tp->snd_max)) {
  789.               tcpstat.tcps_rcvacktoomuch++;
  790.               goto dropafterack;
  791. --- 885,894 ----
  792.                * the congestion window was inflated to account for
  793.                * the other side's cached packets - retract it.
  794.                */
  795. !             if (tp->snd_cwnd > tp->snd_ssthresh)
  796. !                 tp->snd_cwnd = tp->snd_ssthresh;
  797. !             tp->t_dupacks = 0;
  798.           }
  799.           if (SEQ_GT(ti->ti_ack, tp->snd_max)) {
  800.               tcpstat.tcps_rcvacktoomuch++;
  801.               goto dropafterack;
  802.  
  803. 12) Can I use a single bit subnet?
  804.  
  805. A)  It would seem that the consensus is no.  The best citable answer
  806. follows.
  807.  
  808. >From RFC1122:
  809.       "3.3.6  Broadcasts
  810.          Section 3.2.1.3 defined the four standard IP broadcast address
  811.          forms:
  812.            Limited Broadcast:  {-1, -1}
  813.            Directed Broadcast:  {<Network-number>,-1}
  814.            Subnet Directed Broadcast:
  815.                               {<Network-number>,<Subnet-number>,-1}
  816.            All-Subnets Directed Broadcast: {<Network-number>,-1,-1}"
  817.  
  818. All-Subnets Directed broadcasts are being deprecated in favor of IP
  819. multicast, but were very much defined at the time RFC1122 was written.
  820. Thus a Subnet Directed Broadcast to a subnet of all ones is not
  821. distinguishable from an All-Subnets Directed Broadcast.
  822.  
  823. For those old systems that used all zeros for broadcast in IP addresses,
  824. a similar argument can be made against the subnet of all zeros.
  825.  
  826. Also, for old routing protocols like RIP, a route to subnet zero
  827. is not distinguishable from the route to the entire network number
  828. (except possibly by context).
  829.  
  830. Most of today's systems don't support variable length subnet masks
  831. (VLSM), and for such systems the above is true. However, all the major
  832. router vendors and *some* Unix systems (BSD 4.4 based ones) support
  833. VLSMs, and in that case the situation is more complicated :-)
  834.  
  835. With VLSMs (necessary to support CIDR, see RFC 1519), you can utilize the
  836. address space more efficiently. Routing lookups are based on *longest*
  837. match, and this means that you can for instance subnet the class C net
  838. with a mask of 255.255.255.224 (27 bits) in addition to the subnet mask
  839. of 255.255.255.192 (26 bits) given above. You will then be able to use
  840. the addresses x.x.x.33 through x.x.x.62 (first three bits 001) and the
  841. addresses x.x.x.193 through x.x.x.222 (first three bits 110) with this
  842. new subnet mask. And you can continue with a subnet mask of 28 bits, etc.
  843. (Note also, by the way, that non-contiguous subnet masks are deprecated.)
  844.  
  845. This is all very nicely covered in the paper by Havard Eidnes:
  846.  
  847.   Practical Considerations for Network Address using a CIDR Block Allocation
  848.   Proceedings of INET '93
  849.  
  850. This paper is available with anonymous FTP from
  851.  
  852.     aun.uninett.no:/pub/misc/eidnes-cidr.ps
  853.  
  854. The same paper, with minor revisions, is one of the articles in the
  855. special Internetworking issue of Communications of the ACM (last month,
  856. I believe).
  857.  
  858. > I have be told that some network equipment (Cisco I think was the vendor 
  859. > named) will not correctly handle subnets that violated that standard.
  860. As far as I know cisco is one of the router vendors that *do* handle
  861. VLSMs correctly. Could you substantiate this claim?
  862.  
  863. Steinar Haug, SINTEF RUNIT, University of Trondheim, NORWAY
  864. Email: Steinar.Haug@runit.sintef.no
  865.  
  866.